package org.example.day03;

import java.util.Scanner;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO+
 * <p>  RSA加密算法在网络安全世界中无处不在，它利用了极大整数因数分解的困难度，数据越大，安全系数越高，给定一个<span>32</span>位正整数，请对其进行因数分解，找出是哪两个素数的乘积。 </p>
 *
 * RSA加密算法在网络安全世界中无处不在，它利用了极大整数因数分解的困难度，数据越大，安全系数越高，给定一个32位正整数，请对其进行因数分解，找出是哪两个素数的乘积。
 * @date 2024/3/11 15:22
 */
public class test047  {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入的正整数
        int num = scanner.nextInt();

        // 调用因数分解函数进行计算
        int[] result = factorize(num);

        // 输出结果
        System.out.println(result[0] + " " + result[1]);
    }

    // 判断一个数是否为素数
    private static boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }

        if (num == 2) {
            return true;
        }

        if (num % 2 == 0) {
            return false;
        }

        // 从3到sqrt(num)遍历奇数，判断是否能整除num
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }

    // 因数分解
    private static int[] factorize(int num) {
        int prime1 = -1;
        int prime2 = -1;

        // 从2到sqrt(num)遍历，找到满足num能被i整除且i和num/i均为素数的i
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0 && isPrime(i) && isPrime(num / i)) {
                prime1 = i;
                prime2 = num / i;
                break;
            }
        }

        if (prime1 != -1 && prime2 != -1) {
            return new int[]{prime1, prime2};
        } else {
            return new int[]{-1, -1};
        }
    }
}

